package com.zwj.interview.哈希表;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * 设计一个数据结构，使如下3个操作的时间复杂度都是O（1）。
 * ● insert（value）：如果数据集中不包含一个数值，则把它添加到数据集中。
 * ● remove（value）：如果数据集中包含一个数值，则把它删除。
 * ● getRandom()：随机返回数据集中的一个数值，要求数据集中每个数字被返回的概率都相同(这个使用数组加随机数可以实现)
 */
@Deprecated
public class 设计一个数据结构操作为O1 {

    //HashMap的键是数值，而对应的值为它在数组中的位置
    HashMap<Integer, Integer> numToLocation;

    ArrayList<Integer> nums;

    public 设计一个数据结构操作为O1() {
        this.numToLocation = new HashMap<>();
        this.nums = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (numToLocation.containsKey(val)) {
            return false;
        }
        numToLocation.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!numToLocation.containsKey(val)) {
            return false;
        }
        int location = numToLocation.get(val);
        /**
         * 从数组中用O（1）的时间删除一个数字要稍微麻烦一点。需要先从哈希表中得到待删除的数字的下标，
         * 但不能直接把该数字删除。这是因为待删除的数字不一定位于数组的尾部。当数组中间的数字被删除之后，
         * 为了确保数组内存的连续性，被删除的数字后面的数字会向前移动以填补被删除的内容空缺。
         * 由于被删除的数字后面的所有数字都需要移动，因此删除的时间复杂度就是O（n）
         *
         *为了避免在数组中删除数字的时候移动数据，可以把被删除的数字和数组尾部的数字交换，再删除数组最后的数字。由于被删除的数字已经位于数组的尾部，此时删除就不会引起数据移动，因此时间复杂度仍然是O（1）
         *
         */
        //先拿到要删除数字在数组中的下标值，因为要删除的数字不一定就是数组的最后一位，所以不能直接删除，需要
        //将要删除的数字和最后一位进行交换下标，这样的目的就是避免数组在删除后形成空洞
        /**
         * 拿到数组中最后一个数字，将其放到待删除的数字位置上,这里就是为了和后面的
         * nums.set(location, nums.get(nums.size() - 1))对应起来
         */
        numToLocation.put(nums.get(nums.size() - 1), location);
        numToLocation.remove(val);
        //------操作数组------------------
        //将最后一位数字放在要删除元素的位置上
        nums.set(location, nums.get(nums.size() - 1));
        //上一步我们已经把最后一个元素移到了待删除元素的位置上，接下来只需要将数组中删除最后一个元素
        nums.remove(nums.size() - 1);
        return true;
    }

    public int getRandom() {
        Random random = new Random();
        int r = random.nextInt(nums.size());
        return nums.get(r);
    }
}
